package com.mj.Trie;

import java.util.HashMap;

/**
 * @Author: LDeng
 * @Date: 2021-03-19 13:21
 */
public class Trie<V> {

    private int size;

    private Node<V> root;

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        size = 0;
        root=null;
    }

    public V get(String key) {
        Node<V> node = getNodeByKey(key);
        return (node!=null && node.word)?node.value:null;
    }

    public boolean contains(String key) {
        Node<V> node = getNodeByKey(key);
        return node!= null && node.word;//不为空， 并且是一个单词->红色节点
    }

    public V add(String key, V value) {
        keyCheck(key);
        //创建根节点
        if(root==null){
            root=new Node<>(null);
        }
        Node<V> node = root;
        int len = key.length();
        for (int i = 0; i < len; i++) {
            char c = key.charAt(i);
            boolean emptyChildren=node.children==null;//没有children
            Node<V> childNode = emptyChildren?null:node.children.get(c);//字符c对应的children
            if (childNode == null) {
                childNode = new Node<>(node);
                childNode.character=c;
                node.children=emptyChildren?new HashMap<Character, Node<V>>():node.children;
                node.children.put(c, childNode);
            }
            node=childNode;
        }
        if (node.word) {
            //覆盖
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }
        //新增一个单词
        node.word = true;
        node.value = value;
        size++;
        return null;
    }

    public V remove(String key) {
        //找到最后一个节点
        Node<V> node=getNodeByKey(key);
        //如果为空或者不是单词结尾，不做处理
        if(node==null||!node.word) return null;
        size--;
        V oldValue=node.value;
        //最后一个节点是否还有子节点，=> 节点变成蓝色即可
        if(node.children!=null&&!node.children.isEmpty()){
            node.word=false;
            node.value=null;
            return oldValue;
        }
        //如果没有子节点,
        // 1，向上删除到有多个子节点的节点
        // 2, 父节点是一个单词的结尾(红节点)
        Node<V> parent=null;
        while ((parent=node.parent)!=null){
            parent.children.remove(node.character);
            if(parent.word||!parent.children.isEmpty()) break;//删除到有多个子节点的父节点
            node=parent;
        }
        return oldValue;
    }

    public boolean startsWith(String prefix) {
      return getNodeByKey(prefix)!=null;
    }

    private static class Node<V> {
        Node<V> parent;
        Character character;
        HashMap<Character, Node<V>> children;
        V value;
        boolean word;//是否为单词的结尾

        public Node(Node<V> parent) {
            this.parent = parent;
        }
    }

    private Node<V> getNodeByKey(String key) {
        keyCheck(key);
        Node<V> node = root;
        int len = key.length();
        for (int i = 0; i < len; i++) {
            if (node == null ||node.children==null||node.children.isEmpty()) return null;
            char c = key.charAt(i);// d o g...
            node = node.children.get(c);
        }
        return node;
    }

    private void keyCheck(String key) {
        if (key == null || key.length() == 0) {
            throw new IllegalArgumentException("key must not be empty");
        }
    }

}
